


#include <iostream>
#include <string>
using namespace std;

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
 
class Solution
{
public:
    void reorderList(ListNode* head)
    {
        if (!head->next || !head->next->next)
            return;

        ListNode* prev = nullptr;
        ListNode* slow = head, * fast = head;

        while (fast && fast->next)
        {
            prev = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        prev->next = nullptr;

        ListNode* head1 = head, * head2 = ReverseList(slow);
        while (head1 && head2)
        {
            ListNode* next1 = head1->next, * next2 = head2->next;

            head1->next = head2;
            head1 = next1;
            head2->next = head1;
            prev = head2;
            head2 = next2;
        }
        if (head2)
            prev->next = head2;
    }

    char dismantlingAction(string arr)
    {
        char res = ' ';
        int n = arr.size(), hash[26] = { 0 };

        for (const auto& e : arr)
        {
            ++hash[e - 'a'];
        }
        for (int i = 0; i < n; ++i)
        {
            if (1 == hash[arr[i] - 'a'])
            {
                res = arr[i];
                break;
            }
        }

        return res;
    }

private:
    ListNode* ReverseList(ListNode* head)
    {
        ListNode* cur = head, * prev = nullptr;

        while (cur)
        {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }

        return prev;
    }
};

int main()
{

	return 0;
}